{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #N-ary Tree Preorder Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #depth-first-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #深度优先搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: preorder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #N 叉树的前序遍历"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 n&nbsp;叉树的根节点 <meta charset=\"UTF-8\" />&nbsp;<code>root</code>&nbsp;，返回 <em>其节点值的<strong> 前序遍历</strong></em> 。</p>\n",
    "\n",
    "<p>n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 <code>null</code> 分隔（请参见示例）。</p>\n",
    "\n",
    "<p><br />\n",
    "<strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png\" style=\"height: 193px; width: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,3,2,4,null,5,6]\n",
    "<strong>输出：</strong>[1,3,5,6,2,4]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png\" style=\"height: 272px; width: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]\n",
    "<strong>输出：</strong>[1,2,3,6,7,11,14,4,8,12,5,9,13,10]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>节点总数在范围<meta charset=\"UTF-8\" />&nbsp;<code>[0, 10<sup>4</sup>]</code>内</li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li>n 叉树的高度小于或等于 <code>1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>递归法很简单，你可以使用迭代法完成此题吗?</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [n-ary-tree-preorder-traversal](https://leetcode.cn/problems/n-ary-tree-preorder-traversal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [n-ary-tree-preorder-traversal](https://leetcode.cn/problems/n-ary-tree-preorder-traversal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,null,3,2,4,null,5,6]', '[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "#     def helper(self, root: 'Node') -> List[int]:\n",
    "#         if root is None: return []\n",
    "#         result = []\n",
    "#         for child in root.children:\n",
    "#             result.append(child.val)\n",
    "#             result = result + self.helper(child)\n",
    "#         return result\n",
    "        \n",
    "#     def preorder(self, root: 'Node') -> List[int]:\n",
    "#         if root is None: return []\n",
    "#         return [root.val] + self.helper(root)\n",
    "    \n",
    "    # # more concise\n",
    "    # def preorder(self, root: 'Node') -> List[int]:\n",
    "    #     if root is None: return []\n",
    "    #     result = [root.val]\n",
    "    #     for child in root.children:\n",
    "    #         result = result + self.preorder(child)\n",
    "    #     return result\n",
    "    \n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        queue = collections.deque([root])\n",
    "        result = []\n",
    "        while queue:\n",
    "            curr = queue.pop()\n",
    "            result.append(curr.val)\n",
    "            for child in curr.children[::-1]:\n",
    "                queue.append(child)\n",
    "        return result     \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, children):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def preorder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: Node\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        ret = []\n",
    "        if root is None:\n",
    "            return ret\n",
    "        stack = [root]\n",
    "        while len(stack) != 0:\n",
    "            node = stack.pop()\n",
    "            ret.append(node.val)\n",
    "            if node.children:\n",
    "                for _ in reversed(node.children):\n",
    "                    stack.append(_)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, children):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def preorder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: Node\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        stack, res = [root,], []\n",
    "        \n",
    "        while stack:\n",
    "            root = stack.pop()\n",
    "            res.append(root.val)\n",
    "            stack.extend(root.children[::-1])\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, children):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        if root == None:\n",
    "            return []\n",
    "        re = []\n",
    "        stack = [root]\n",
    "        while len(stack)>0:\n",
    "            node = stack.pop()\n",
    "            re.append(node.val)\n",
    "            for i in range(len(node.children)):\n",
    "                child = node.children[len(node.children)-i-1]\n",
    "                if child!=None:\n",
    "                    stack.append(child)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, children):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> 'List[int]':      \n",
    "        # if root==None:\n",
    "        #     return []\n",
    "        # r=[root.val]\n",
    "        # for each in root.children:\n",
    "        #     r+=self.preorder(each)\n",
    "        # return r\n",
    "        if root==None:\n",
    "            return []\n",
    "        res=[]\n",
    "        stack=[root]\n",
    "        while stack:\n",
    "            cur=stack.pop(0)\n",
    "            res.append(cur.val)\n",
    "            stack=cur.children+stack\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    \n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        res = []\n",
    "        if(root ==None) : return res\n",
    "        def preo(root : 'Node', res):\n",
    "            res.append(root.val)\n",
    "            for chid in root.children:\n",
    "                preo(chid,res)\n",
    "        preo(root,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        if root is None: return\n",
    "        stack, output = [root,],[]\n",
    "\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            output.append(node.val)\n",
    "            stack.extend(node.children[::-1])\n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        res = []\n",
    "\n",
    "        if root:\n",
    "            res.append(root.val)\n",
    "            for child in root.children:\n",
    "                root = res.extend(self.preorder(child))\n",
    "        \n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        nodes = []\n",
    "        def _preorder(root: 'Node') -> None:    \n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            nodes.append(root.val)\n",
    "            for node in root.children:\n",
    "                _preorder(node)\n",
    "\n",
    "        _preorder(root)\n",
    "        return nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        output = []\n",
    "\n",
    "        def helper(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            output.append(node.val)\n",
    "            for n in node.children:\n",
    "                helper(n)\n",
    "        helper(root)\n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        ans = []\n",
    "        def order(root,ans):\n",
    "            if not root:\n",
    "                return\n",
    "            ans.append(root.val)\n",
    "            if root.children:\n",
    "                for node in root.children:\n",
    "                    order(node,ans)\n",
    "        order(root,ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        stack,ans = [root],[]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            ans.append(node.val)\n",
    "            if node.children:\n",
    "                stack.extend(reversed(node.children))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        result=[]\n",
    "\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                print(root.val)\n",
    "                result.append(root.val)\n",
    "                for child in root.children:\n",
    "                    dfs(child)\n",
    "\n",
    "        dfs(root)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        result=[]\n",
    "        def pred(node):\n",
    "            if not node:\n",
    "                return\n",
    "            vals=node.val\n",
    "            result.append(vals)\n",
    "            for child in node.children:\n",
    "                pred(child)\n",
    "        pred(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        res  = []\n",
    "        def pre(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            res.append(root.val)\n",
    "            for no in root.children:\n",
    "                pre(no)\n",
    "        pre(root)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        #从 https://leetcode.cn/leetbook/read/n-ary-tree/x0locc/ 进入\n",
    "        #迭代，栈\n",
    "        if not root:#空\n",
    "            return []\n",
    "        out = []\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            out.append(cur.val)\n",
    "            if cur.children:\n",
    "                stack += cur.children[::-1]\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        result = []\n",
    "\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return \n",
    "\n",
    "            result.append(root.val)\n",
    "            for child in root.children:\n",
    "                helper(child)\n",
    "\n",
    "        helper(root)\n",
    "        return result\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        stack = []\n",
    "        res = []\n",
    "\n",
    "        while root or stack:\n",
    "            while root:\n",
    "                res.append(root.val)\n",
    "                stack.append((root,0))\n",
    "                if root.children:\n",
    "                    root = root.children[0]\n",
    "                else:\n",
    "                    root = None\n",
    "            \n",
    "            cur, index =  stack.pop()\n",
    "\n",
    "            if cur.children and index != len(cur.children) - 1:\n",
    "                stack.append((cur, index + 1))\n",
    "                root = cur.children[index + 1]\n",
    "        \n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        def traversal(root, res):\n",
    "            if root == None: return \n",
    "            res.append(root.val)\n",
    "            for i in range(len(root.children)):\n",
    "                traversal(root.children[i], res)\n",
    "        res = []\n",
    "        traversal(root, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        self.ans=[]\n",
    "        def f(r,c):\n",
    "            if r:\n",
    "                if len(self.ans)!=c+1:\n",
    "                    self.ans.append([r.val])\n",
    "                else:\n",
    "                    self.ans[c].append(r.val)\n",
    "                for i in r.children:\n",
    "                    f(i,c+1)\n",
    "        f(root,0)\n",
    "        return [j for i in self.ans for j in i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        res=[]\n",
    "        #前序遍历\n",
    "        def preorder1(root):\n",
    "            #各个节点的值入队\n",
    "            if root:\n",
    "               res.append(root.val)\n",
    "               #递归遍历\n",
    "               for node in root.children:\n",
    "                   preorder1(node)\n",
    "        preorder1(root)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        res = []\n",
    "        if not root:\n",
    "            return res\n",
    "        def in_preorder(root, res):\n",
    "            res.append(root.val)\n",
    "            for i in root.children:\n",
    "                in_preorder(i, res)\n",
    "        in_preorder(root, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def preorder(self, root: 'Node') -> List[int]:\n",
    "        def bl(r=Node()):\n",
    "            if not r:return []\n",
    "            l=[]\n",
    "            for i in r.children:\n",
    "                l=l+bl(i)\n",
    "            return [r.val]+l\n",
    "        return bl(root)\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
